home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / basic / ubmalm.zip / peralta.ub < prev    next >
Text File  |  1990-08-22  |  802b  |  24 lines
  1.  1070   *Peralta(P,X,&S)
  2.  1080   ' Computes a square root of the quadratic residue X, modulo
  3.  1090   ' the odd prime P, returning the result in S.
  4.  1100   ' 15 May 1990
  5.  1110   local R,Q,U,V,A,B,Te,Qq
  6.  1120   if P@4=3 then S=modpow(X,(P+1)\4,P):return endif
  7.  1130   R=0:Q=(P-1)\2
  8.  1140   while even(Q):Q=Q\2 wend
  9.  1150   repeat
  10.  1160   repeat inc R:until (R*R+X)@P<>0
  11.  1170   U=1:V=0:A=R:B=1:Qq=Q
  12.  1180   while Qq<>0
  13.  1190   if odd(Qq) then Te=(U*A-B*V*X)@P:V=(A*V+U*B)@P:U=Te endif
  14.  1200   Qq=Qq\2:Te=(A*A-B*B*X)@P:B=(2*A*B)@P:A=Te
  15.  1210   wend
  16.  1220   until and{U<>0,V<>0}
  17.  1230   A=U:B=V
  18.  1240   U=(A*A-B*B*X)@P:V=(2*A*B)@P
  19.  1250   while U<>0
  20.  1260   A=U:B=V:U=(A*A-B*B*X)@P:V=(2*A*B)@P
  21.  1270   wend
  22.  1280   S=modinv(B,P):S=(A*S)@P
  23.  1290   return ' End of subroutine Peralta.
  24.